// https://www.lintcode.com/problem/edit-distance/

public class Solution {
    /**
     * @param word1: A string
     * @param word2: A string
     * @return: The minimum number of steps.
     */
    public int minDistance(String word1, String word2) {
        // write your code here
        cache = new int[word1.length()][word2.length()];
        for (int i = 0; i < cache.length; ++i) {
            Arrays.fill(cache[i], -1);
        }
        return _minDistance(word1, 0, word2, 0);
    }

    protected int _minDistance(String word1, int idx1, String word2, int idx2) {
        if (idx1 >= word1.length()) {
            return word2.length() - idx2;
        } else if (idx2 >= word2.length()) {
            return word1.length() - idx1;
        }
        if (cache[idx1][idx2] == -1) {
            // 假设通过插入一个与另一方相同位置一样的字符
            int d1 = 1 + Math.min(_minDistance(word1, idx1 + 1, word2, idx2), _minDistance(word1, idx1, word2, idx2 + 1));
            // 相同位置如果不同，做一次字符改变，继续处理后面的字符串。
            int d2 = _minDistance(word1, idx1 + 1, word2, idx2 + 1);
            if (word1.charAt(idx1) != word2.charAt(idx2)) {
                ++d2;
            }
            cache[idx1][idx2] = Math.min(d1, d2);
        }
        return cache[idx1][idx2];
     }

    private int[][] cache;
}